//
//  StringMultiply.swift
//  LeetCodeDemo
//
//  Created by 杨冬武 on 2021/3/20.
//

import Foundation

/*
 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

 示例 1:

 输入: num1 = "2", num2 = "3"
 输出: "6"

 示例 2:

 输入: num1 = "123", num2 = "456"
 输出: "56088"

 说明：

     num1 和 num2 的长度小于110。
     num1 和 num2 只包含数字 0-9。
     num1 和 num2 均不以零开头，除非是数字 0 本身。
     不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/multiply-strings
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

class StringMultiply {
    func multiply(_ num1: String, _ num2: String) -> String {
        guard num1 != "0", num2 != "0" else {
            return "0"
        }
        let num1 = [Character](num1), num2 = [Character](num2)
        let m = num1.count, n = num2.count
        var ansArr = [Int](repeating: 0, count: m + n)
        //相乘放入数组
        for i in (0..<m).reversed() {
            let x = num1[i].toInt()
            for j in (0..<n).reversed() {
                let y = num2[j].toInt()
                ansArr[i + j + 1] += x * y
            }
        }
        //处理进位
        for i in (1..<m + n).reversed() {
            ansArr[i - 1] += ansArr[i] / 10
            ansArr[i] = ansArr[i] % 10
        }
        var ans = String()
        var index = ansArr[0] == 0 ? 1 : 0
        while index < m + n {
            ans.append("\(ansArr[index])")
            index += 1
        }
        return ans
    }
    
    func test() {
        let res = multiply("456", "123")
        print(res)
    }
}



/*
 边界条件: 有"0"直接返回"0"
 乘积的长度为 m+n−1 或 m+n
 创建长度为 m+n 的数组 ansArr 用于存储乘积。
 乘数 j 位乘以被乘数 i 位, 存储到 i+j+1 位, 进位存储到 i+j 位
 高位是 0 移除

*/
